package org.algorithm.Sort;

public class MergeSort {
    // 归并排序算法的入口方法
    public static void mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        // 创建一个辅助数组，用于在归并过程中临时存储数据
        int[] helper = new int[array.length];
        // 调用归并排序的递归方法
        mergeSort(array, helper, 0, array.length - 1);
    }

    // 归并排序的递归方法
    private static void mergeSort(int[] array, int[] helper, int low, int high) {
        if (low < high) {
            int middle = (low + high) / 2; // 计算数组的中间索引
            mergeSort(array, helper, low, middle); // 对左半部分进行递归排序
            mergeSort(array, helper, middle + 1, high); // 对右半部分进行递归排序
            merge(array, helper, low, middle, high); // 合并两个有序数组
        }
    }

    // 合并两个有序数组的方法
    private static void merge(int[] array, int[] helper, int low, int middle, int high) {
        // 将待排序的数组复制到辅助数组中
        for (int i = low; i <= high; i++) {
            helper[i] = array[i];
        }

        // 初始化左右两个半部分的起始索引
        int helperLeft = low;
        int helperRight = middle + 1;
        int current = low;

        // 比较两个半部分的元素，依次将较小的元素放入原数组中
        while (helperLeft <= middle && helperRight <= high) {
            if (helper[helperLeft] <= helper[helperRight]) {
                array[current] = helper[helperLeft];
                helperLeft++;
            } else {
                array[current] = helper[helperRight];
                helperRight++;
            }
            current++;
        }

        // 将剩余元素拷贝到原数组中
        int remaining = middle - helperLeft;
        for (int i = 0; i <= remaining; i++) {
            array[current + i] = helper[helperLeft + i];
        }
    }

    // 主方法用于测试归并排序
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        mergeSort(array);
        System.out.println("Sorted array:");
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}
